//The MIT License
//
//Copyright (c) 2009 nodchip
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in
//all copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
//THE SOFTWARE.
package tv.dyndns.kishibe.server.relevance;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Map.Entry;
import java.util.concurrent.Callable;

import tv.dyndns.kishibe.client.packet.PacketProblemData;
import tv.dyndns.kishibe.server.CachedDatabase;
import tv.dyndns.kishibe.server.util.Pair;
import tv.dyndns.kishibe.server.util.ParallelComputation;

public class RelevantProblem {
	public static class Characteristic {
		public int problemId = 0;
		public final List<Pair<String, Double>> vector = new ArrayList<Pair<String, Double>>();
		public double abs = 0;
	}

	private volatile int numberOfDocuments = 0;
	private final Map<String, Integer> numberOfDocumentsContainWord = new HashMap<String, Integer>();
	private final List<Characteristic> characteristics = new ArrayList<Characteristic>();
	private Object lock = new Object();
	private Trie trie;
	private final ParallelComputation parallelComputation = ParallelComputation.createInstance();

	public void update() throws Exception {
		synchronized (lock) {
			if (trie == null) {
				trie = new Trie();
			}

			numberOfDocuments = 0;
			numberOfDocumentsContainWord.clear();
			characteristics.clear();

			// ドキュメント数と逆出現頻度を計算する
			CachedDatabase.getInstance().processProblems(sentencesProcessorIdfCalculation);

			CachedDatabase.getInstance().processProblems(sentencesProcessorCaracteristics);
		}
	}

	private boolean isValidWord(String word) {
		final int length = word.length();
		if (length <= 1) {
			return false;
		}

		// ○のみからなる文字列は無視
		boolean isCircles = true;
		for (int i = 0; i < length && isCircles; ++i) {
			isCircles = word.charAt(i) == '○';
		}
		if (isCircles) {
			return false;
		}

		return true;
	}

	private final SentencesProcessor sentencesProcessorIdfCalculation = new SentencesProcessor() {
		@Override
		public void process(String sentence, int problemId) throws Exception {
			final Set<String> words = new HashSet<String>();

			if (sentence == null || sentence.isEmpty()) {
				return;
			}

			final List<String> nouns = new ArrayList<String>();
			trie.parse(sentence, nouns);

			for (String noun : nouns) {
				if (!isValidWord(noun)) {
					continue;
				}

				words.add(noun);
			}

			for (String word : words) {
				int value = 1;
				if (numberOfDocumentsContainWord.containsKey(word)) {
					value = numberOfDocumentsContainWord.get(word) + 1;
				}
				numberOfDocumentsContainWord.put(word, value);
			}

			++numberOfDocuments;
		}
	};
	private final SentencesProcessor sentencesProcessorCaracteristics = new SentencesProcessor() {
		@Override
		public void process(String sentences, int problemId) throws Exception {
			characteristics.add(createCharacteristic(sentences, problemId));
		}
	};

	private Characteristic createCharacteristic(String sentence, int problemId) throws Exception {
		// 単語数と単語の出現頻度を計算する
		if (sentence == null || sentence.isEmpty()) {
			return null;
		}

		int numberOfWords = 0;
		final Map<String, Integer> numberOfOccurrences = new HashMap<String, Integer>();

		final List<String> words = new ArrayList<String>();
		trie.parse(sentence, words);

		for (String word : words) {
			if (!isValidWord(word)) {
				continue;
			}

			int value = 1;
			if (numberOfOccurrences.containsKey(word)) {
				value = numberOfOccurrences.get(word) + 1;
			}
			numberOfOccurrences.put(word, value);
			++numberOfWords;
		}

		final Characteristic characteristic = new Characteristic();
		characteristic.problemId = problemId;

		// 各単語のtfidfを計算する
		for (Entry<String, Integer> entry : numberOfOccurrences.entrySet()) {
			final String word = entry.getKey();
			final int numberOfOccurrence = entry.getValue();

			if (!numberOfDocumentsContainWord.containsKey(word)) {
				continue;
			}

			final double tfidf = (double) numberOfOccurrence / numberOfWords * Math.log((double) numberOfDocuments / numberOfDocumentsContainWord.get(word));
			characteristic.vector.add(new Pair<String, Double>(word, tfidf));
			characteristic.abs += tfidf * tfidf;
		}
		Collections.sort(characteristic.vector);
		characteristic.abs = Math.sqrt(characteristic.abs);
		return characteristic;
	}

	private static final int NUMBER_OF_RESULTS = 10;

	public List<Integer> search(String sentence) throws Exception {
		synchronized (lock) {
			if (trie == null) {
				update();
			}

			final Characteristic a = createCharacteristic(sentence, -1);
			final Queue<Pair<Double, Integer>> queue = new PriorityQueue<Pair<Double, Integer>>();
			final List<Callable<Void>> tasks = new ArrayList<Callable<Void>>();

			for (final Characteristic characteristic : characteristics) {
				tasks.add(new Callable<Void>() {
					@Override
					public Void call() throws Exception {
						double similarity = 0;
						Iterator<Pair<String, Double>> it = a.vector.iterator();
						Iterator<Pair<String, Double>> jt = characteristic.vector.iterator();

						if (!it.hasNext() || !jt.hasNext()) {
							return null;
						}

						Pair<String, Double> i = it.next();
						Pair<String, Double> j = jt.next();
						while (true) {
							final int compareTo = i.first.compareTo(j.first);
							if (compareTo == 0) {
								similarity += i.second * j.second;

								if (!it.hasNext() || !jt.hasNext()) {
									break;
								}
								i = it.next();
								j = jt.next();

							} else if (compareTo < 0) {
								if (!it.hasNext()) {
									break;
								}
								i = it.next();

							} else {
								if (!jt.hasNext()) {
									break;
								}
								j = jt.next();
							}
						}

						synchronized (queue) {
							queue.add(new Pair<Double, Integer>(similarity, characteristic.problemId));
							while (queue.size() > NUMBER_OF_RESULTS) {
								queue.remove();
							}
						}

						return null;
					}
				});
			}
			parallelComputation.execute(tasks);

			final List<Integer> results = new ArrayList<Integer>();
			while (!queue.isEmpty()) {
				results.add(queue.remove().second);
			}

			return results;
		}
	}

	public static void main(String[] args) throws Exception {
		long beginTime, endTime;

		beginTime = System.currentTimeMillis();
		RelevantProblem relevantProblem = new RelevantProblem();
		relevantProblem.update();
		endTime = System.currentTimeMillis();

		System.out.println("経過時間:" + (endTime - beginTime) + "(ms)");

		beginTime = System.currentTimeMillis();
		final List<Integer> indexes = relevantProblem.search("少年時代から無鉄砲な江戸っ子の坊っちゃんと、肉親から疎んじられる彼に無償の愛を注ぐ女中である清の描写から『坊っちゃん』の物語は幕を開く。坊っちゃんは両親と死別後、清とも離れ、四国の旧制中学校に数学の教師として赴任する。着任早々、校長には狸、教頭には赤シャツ、画学の教師には野だいこ、英語の教師にはうらなり、数学の主任教師には山嵐と、それぞれにあだ名を付けた。坊っちゃんは授業の時に生徒達から、てんぷらそばを四杯食べた件等の私事について執拗に冷やかされる。また初めての宿直の夜には、寄宿生達から蒲団の中に大量のバッタ（厳密にはイナゴ）を入れられる等の嫌がらせを受け、激怒して、何としても犯人を突き止めようとしたため、大事になってしまう。坊っちゃんは赤シャツとその腰巾着である野だいこから、生徒による嫌がらせは山嵐の扇動によるものであると婉曲的に吹き込まれ、一時は真に受けてしまう。しかし、後日の職員会議において、先の寄宿生の不祥事に坊っちゃんが毅然とした措置を主張したところ、狸をはじめとする事なかれ主義の職員達は取り合ってくれなかったのに対し、山嵐だけが坊っちゃんを支持してくれた。お互いに対する誤解は解けていき、坊っちゃんと山嵐とは、かえって強い友情で結ばれるようになる。うらなりには、マドンナとあだ名される婚約者がいたが、赤シャツがマドンナへの横恋慕から、お人好しのうらなりを体良く延岡に左遷したという事実を知り、坊っちゃんは義憤にかられる。実は山嵐も、赤シャツの横恋慕を糾弾したため、逆恨みされていたのであった。日露戦争の祝勝会の日に、坊っちゃんと山嵐は赤シャツの謀略により、中学校と師範学校の生徒同士の乱闘騒ぎに巻き込まれた上、いわれ無き生徒扇動の罪を着せられ、山嵐が辞職に追い込まれる。卑劣な仕打ちに憤激した坊っちゃんと山嵐は、赤シャツと野だいこの不祥事を暴くための監視を始め、ついに芸者遊び帰りの赤シャツと野だいこを取り押さえる。そして芸者遊びについて詰問するも、しらを切られたため、業を煮やし、激しく暴行を加えた。即刻辞職した坊っちゃんは、帰郷後、街鉄（現在の都電）の技手となって、再び、清と同居生活を始めるが、清が亡くなり、遺言通り小日向の養源寺に葬った事を記して、『坊っちゃん』の物語は幕を閉じる。");
		endTime = System.currentTimeMillis();

		for (PacketProblemData problemData : CachedDatabase.getInstance().getProblemData(indexes)) {
			System.out.println(problemData.toString());
		}

		System.out.println("経過時間:" + (endTime - beginTime) + "(ms)");

		System.exit(0);
	}
}
